#include<iostream>
#include<stdlib.h>

using namespace std;

typedef struct Nodo{
    int dato;
    struct Nodo *siguiente;
    struct Nodo *anterior;
}Nodo;

typedef struct{
    Nodo *inicio;
}Lista;


void inicializacion (Lista*tas){
    tas->inicio=NULL;
    return;
}

void inicioLista (Lista*tas,int dato){
    Nodo *nuevoElemento;
    nuevoElemento->dato=dato;
    nuevoElemento->siguiente=NULL;
    nuevoElemento->anterior=NULL;
    tas->inicio=nuevoElemento;
    return;
}

void enlistarFinal (Lista*tas,int dato){
    Nodo *nuevoElemento;
    Nodo *actual;
    if ((nuevoElemento =(Nodo*)malloc(sizeof(Nodo)))==NULL)
        return;
    nuevoElemento->dato=dato;
    nuevoElemento->siguiente=NULL;
    actual=tas->inicio;
    while (1)
    {
        if (!actual->siguiente)break;
        actual=actual->siguiente;
    }
    actual->siguiente=nuevoElemento;
    nuevoElemento->anterior=actual;
    return;
}

void enlistarComienzo(Lista*tas,int dato){
    Nodo *nuevoElemento;
    if ((nuevoElemento =(Nodo*)malloc(sizeof(Nodo)))==NULL)
        return;
    nuevoElemento->dato=dato;
    nuevoElemento->anterior=NULL;
    nuevoElemento->siguiente=tas->inicio;
    tas->inicio=nuevoElemento;
    nuevoElemento->siguiente->anterior=nuevoElemento;
}

void muestra (Lista*tas){
    Nodo*actual;
    actual=tas->inicio;
    if (actual==NULL)return;
    while (1)
    {
        cout<<actual->dato<<endl;
        if (!actual->siguiente)break;
        actual=actual->siguiente;
    }
    return;
}

void desenlistarComienzo (Lista*tas){
    Nodo *sup_elemento;
    if (tas->inicio==NULL)
        return;
    sup_elemento = tas->inicio;
    tas->inicio=tas->inicio->siguiente;
    free(sup_elemento);
    return;
}

void desenlistarFinal (Lista*tas){
    Nodo *sup_elemento;
    Nodo *actual;
    actual=tas->inicio;
    if (actual==NULL)return;
    while (1){
        if (actual->siguiente==NULL) break;
        actual=actual->siguiente;
    }
    sup_elemento=actual;
    actual->anterior->siguiente=NULL;
    free(sup_elemento);
    return;
}

void buscarDato (Lista*tas,int dato){
    int i;
    int flag=0;
    Nodo *actual;
    actual=tas->inicio;
    if (actual==NULL)return;
    for (i=0;i<5;i++){
        if (actual->dato==dato)
            flag=1;
        actual=actual->siguiente;
    }
    if (flag==1)
        cout<<"Se ha encontrado el dato";
    else
        cout<<"No se ha encontrado el dato";
    return;
}

void ordenar (Lista*tas){
    int flag,aux,i;
    Nodo *actual;
    actual=tas->inicio;
    while(1){
            flag=1;
            if ((actual->dato)  >  (actual->siguiente->dato)){
                aux=actual->dato;
                actual->dato=actual->siguiente->dato;
                actual->siguiente->dato=aux;
                flag=0;
            }
            actual=actual->siguiente;
            if (flag==1)
                break;
    }
}

void agregarOrdenado (Lista*tas,int dato){
    Nodo *nuevoElemento;
    Nodo *actual;
    if ((nuevoElemento =(Nodo*)malloc(sizeof(Nodo)))==NULL)
        return;
    nuevoElemento->dato=dato;
    actual=tas->inicio;
    while (1)
    {
        if (actual->dato==dato-1)break;
        actual=actual->siguiente;
    }
    nuevoElemento->siguiente=actual->siguiente;
    nuevoElemento->anterior=actual;
    actual->siguiente->anterior=nuevoElemento;
    actual->siguiente=nuevoElemento;
    return;
}

int main()
{
    Lista *tas;
    int dato;
    int i;
    if ((tas=(Lista*)malloc(sizeof(Lista)))==NULL)
        return -1;
    inicializacion(tas);
    cout<<"Ingrese un numero: ";
    cin>>dato;
    inicioLista (tas,dato);
    for (i=0;i<3;i++){
        cout<<"Ingrese un numero: ";
        cin>>dato;
        enlistarFinal (tas,dato);
        cout<<endl<<"************COMIENZO DE LISTA************"<<endl;
        muestra(tas);
        cout<<endl<<"************FINAL DE LISTA************"<<endl;
    }
    for (i=0;i<3;i++)
    {
        cout<<"Ingrese un numero: ";
        cin>>dato;
        enlistarComienzo(tas,dato);
        cout<<endl<<"************COMIENZO DE LISTA************"<<endl;
        muestra(tas);
        cout<<endl<<"************FINAL DE LISTA************"<<endl;
    }
    cout<<endl<<"Elimino el ultimo nodo";
    desenlistarFinal(tas);
    cout<<endl<<"************COMIENZO DE LISTA************"<<endl;
    muestra (tas);
    cout<<endl<<"************FINAL DE LISTA************"<<endl;
    cout<<endl<<"Elimino el primer nodo";
    desenlistarComienzo(tas);
    cout<<endl<<"************COMIENZO DE LISTA************"<<endl;
    muestra (tas);
    cout<<endl<<"************FINAL DE LISTA************"<<endl;
    cout<<endl<<"Ingrese dato a buscar: ";
    cin>>dato;
    buscarDato(tas,dato);
    ordenar (tas);
    cout<<endl<<"************COMIENZO DE LISTA************"<<endl;
    muestra(tas);
    cout<<endl<<"************FINAL DE LISTA************"<<endl;
    cout<<endl<<"Ingrese un numero: ";
    cin>>dato;
    agregarOrdenado (tas,dato);
    cout<<endl<<"************COMIENZO DE LISTA************"<<endl;
    muestra (tas);
    cout<<endl<<"************FINAL DE LISTA************"<<endl;
    return 1;
}
